CS152 Fall 2008Practice Final

To study for the final I would suggest you: (1) Know how to do (by heart) all the practice problems. (2) Go over your notes at least three times. Second and third time try to see how much you can remember from the first time. (3) Go over the homework problems. (4) Try to create your own problems similar to the ones I have given and solve them. (5) Skim the relevant sections from the book. (6) If you want to study in groups, at this point you are ready to quiz each other. The practice final is below. Here are some facts about the actual final: (a) It is comprehensive (b) It is closed book, closed notes. Nothing will be permitted on your desk except your pen (pencil) and test. (c) You should bring photo ID. (d) There will be more than one version of the test. Each version will be of comparable difficulty. (e) It is 10 problems, 6 problems will be on material since the midterm, four problems will come from the topics covered by prior to the midterm. (f) Two problems will be exactly (less typos) off of the practice final, and one will be off of practice midterm.

1. Give an example showing how to define an interface in Objective-C. Make sure the interface has at least one instance method and at least one class method.

2. What is referential transparency? What is value semantics? Give an example in Scheme (and one in ML) of a higher order function.

3. Show that let blocks, begin blocks, as well as delay, are syntactic sugar for expressions involving lambda abstraction.

4. What is a closure? Give an example of closures in Scheme and another example in ML.

5. Distinguish between (a) a strongly typed language; (b) a weakly typed language. Consider the definition of the natural numbers which says that they are the smallest set such that: (a) 0 is a natural number, (b) if x is a natural number, so is S(x). Express the natural numbers as a datatype in ML.

6. What is Currying? Give an example in ML.

7. What is the difference between an expression and a statement? What is the difference between a procedure and a function?

8. What is Normal Order Evaluation? What is an activation record? What is Pass by Value Result?

9. Briefly describe the Mark and Sweep garbage collection algorithm.

10. Suppose a directed graph g is given as a set of Prolog facts, g(a,b). Each fact indicating one edge in the graph. Write some additional Prolog rules which could be used to determine if node s was connected to node t in this graph.